package com.Offer;

import java.util.ArrayList;
import java.util.List;

/*
    面试题29：顺时针打印矩阵
    输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
    例如，如果输入如下 4X4 矩阵：
    1 2 3 4
    5 6 7 8
    9 10 11 12
    13 14 15 16
    则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
 */
public class demo29 {
    public static void main(String[] args) {
        int[][] input = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        List<Integer> res = spiralOrder(input);
        res.forEach(System.out::println);
    }

    public static List<Integer> spiralOrder(int[][] matrix){
        List<Integer> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0){
            return res;
        }
        int r1 = 0,r2 = matrix.length-1;    //行数
        int c1 = 0,c2 = matrix[0].length-1; //列数

        while(r1 <= r2 && c1 <= c2){
            // 从左往右
            for(int c = c1;c <= c2;c++){
                res.add(matrix[r1][c]);
            }
            // 从上往下
            for(int r = r1+1;r <= r2;r++){
                res.add(matrix[r][c2]);
            }

            if(r1 <r2 && c1 <c2){
                for(int c = c2-1;c > c1;c--){
                    res.add(matrix[r2][c]);
                }

                for(int r = r2;r > r1 ;r--){
                    res.add(matrix[r][c1]);
                }
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return  res;
    }
}
